This invention relates generally to the control of multiple mobile objects to avoid collisions with each other and with other obstacles. More specifically, the invention relates to motion planning and control of multiple robotic manipulators. Robotic manipulators are used in a variety of industrial and commercial applications, to perform tasks such as assembly, disassembly, machining, repair, maintenance and inspection of components. Applications may include sequential or simultaneous combinations of these functions and may involve coordinated motion of multiple manipulators. Basically, a robotic manipulator comprises a tool that is movable to a desired point in three-dimensional space, by means of multiple mechanical links, connected together by joints. The tool, sometimes referred to as an end-effector, may be a gripper, a welding torch, a cutting device, an electromagnet, or other device.
The manipulator may be best visualized in its most common form, in which the tool is connected to a base or frame through a series of rigid mechanical links, which are connected one to the next through joints or gimbals that are simple pivot joints, sometimes referred to as revolute joints. Manipulators may also include other types of joints, involving combinations of sliding and rotational displacement. The positions of the links are defined by multiple joint angles or gimbal angles. A given set of gimbal angles defines a specific position of the tool. Deriving the tool position from a set of gimbal angles is a straightforward problem, usually referred to as involving forward kinetics. A much more difficult problem, involving reverse or inverse kinetics, is the determination of appropriate gimbal angles from a given tool position, which may be defined by multiple sets of gimbal angles.
The present invention pertains to robotic path planning, i.e., the movement of robotic manipulator tools from one point to another in three-dimensional space. Because each position of the tool generally may be defined by any of multiple sets of gimbal angles, the movement of the tool from one position to another may be accomplished over any of multiple paths. One technique for robotic mechanism path planning uses configuration space, sometimes referred to as joint space, instead of Cartesian space, to define the tool positions. The term configuration space (or c-space) will be used in this specification. The tool position in c-space is defined by the gimbal or joint angles. If there are n gimbals, the c-space will have n dimensions. Path planning in c-space has been proposed as a solution for a number of problems that arise in the use of multiple manipulators. See, for example, Lozano-Perez, Spatial Planning: A Configuration Space Approach, IEEE Transactions on Computers, Vol. 32, No. 2, pp. 108-120, February 1983. Fixed obstacles can be "mapped" into c-space so that, in theory, paths can be planned to avoid them, as well as to avoid collisions between manipulator components.
Robotic path planning is an inherently difficult problem for several reasons, such as:
1) The need to perform global planning, that is, to plan a complete move or move sequence from start to end. More local planning often leads to difficulties such as "hunting " for the correct path, dead-end paths, and contention, requiring back-tracking to plan a different path. PA1 2) The need to avoid inadvertent collisions between the manipulators, workpieces on which the tools operate, and the work environment. Collisions can damage the manipulators, the workpieces, or the work environment, causing economic loss or unacceptable safety hazards. PA1 3) The need to work within limited ranges of travel for each axis of each manipulator, since each gimbal may have stops that provide for only a limited range of angular motion. Hitting a gimbal stop may not only halt a current operation, but may also cause physical damage. Manual intervention may be required to restart the operation. PA1 4) The need to resolve the inherent ambiguity in specifying the manipulator gimbal angles to achieve a desired tool location and orientation, i.e., the inverse kinematics problem. PA1 b 5) The need to work within dynamic limitations of the motion, such as limitations in rate, acceleration and jerk. Dynamic limitations arise both from safety concerns and hardware component limitations.
In principle, use of the c-space technique provides a possible solution to the first four of these problems. In practice, however, direct application of the c-space approach results in an excessive computational burden, as explained by Canny, John C., The Complexity of Robot Motion Planning, Ph.D. dissertation, Department of Electrical Engineering and Computer Science, MIT, Cambridge, Mass., May 1987 (also published in book form). For example, using a pure c-space cell approach for a system of three 3-axis manipulators, each axis having a 360E range, and assuming a modest resolution of 0.1E, would require computation and storage of (360/0.1).sup.3+3+3 =3,600.sup.9 or about 10.sup.32 cells. No current or projected technology exists for performing a computation of this magnitude.
Another approach to collision avoidance in robotic manipulators uses an artificial potential or force field analogy to keep manipulator components from colliding. Simply stated, this approach generates manipulator "repulsion" forces based on the relative proximity of the manipulators. The closer that two manipulators are to each other, the greater the repulsion force becomes. Basically, each manipulator is controlled to move along a primary path toward its intended destination, but may be deflected from the path by the repulsion forces generated when the path takes the manipulator too close to another manipulator or too close to a fixed obstacle.
Although using artificial potential fields avoids the computational complexity of the conventional c-space approach, the use of artificial potential fields raises other difficulties. In particular, the potential field for a general manipulator system may have local minima that lead to hunting, including non-periodic oscillations and chaotic motion, dead-ends, stopping at a equalibrium position that is not the desired goal position, and contention, a situation in which the system settles into a limit cycle without reaching the goal position.
It will be appreciated from the foregoing that there is still a need for a technique of path planning for multiple manipulators such that collisions are avoided but the problems associated with c-space path planning and artificial potential collision avoidance are minimized. The present invention satisfies this need.